COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002					Algorithms
C00014 00003			
C00015 ENDMK
C⊗;
				Algorithms


				    by
			      Robert W. Floyd
			      Copyright  l983


An algorithm is the idea of  a particular method of computation, like  the
idea of addition  and subtraction  using carries  and borrows  most of  us
learned in school.  As with  other ideas,  an algorithm  expressed in  one
language can be translated into another; the choice of language is not  an
essential part of  the algorithm.  Familiar algorithms  include those  for
addition, subtraction,  multiplication, and  division; those  for  solving
simultaneous equations by  successive elimination of  variables; that  for
differentiating a formula with respect to a variable; those for estimating
the area under a  curve by approximation with  line segments, etc. One  of
the oldest, due to  Euclid, finds  the  greatest  common  divisor  of  two 
positive numbers:

(1) Let x be the larger number, y the smaller.
(2) If y=0, x is the answer.
(3) Otherwise, let the new value of y be the remainder when  x  is divided 
	by y; let the new value of x be the old value of y. Return to Step
	(2).

Example:  the greatest common divisor of 195 and 75.  Successive values of
x and y are:

	x = 195, y = 75
	x =  75, y = 45
	x =  45, y = 30
	x =  30, y = 15
	x =  15, y =  0

The answer is 15

An algorithm can be expressed in a language intelligible to man,  machine,
or both.  Euclid's algorithm, expressed in a language more suitable to  be
carried out by a machine, looks like:

	GET X
	GET Y
	IF X < Y THEN SWAP X WITH Y
	LABEL A
	IF Y=0 THEN RETURN RESULT = X
	SET R = REMAINDER OF X DIVIDED BY Y
	SET X = Y
	SET Y = R
	GO TO STEP A.

Computers are machines to carry out algorithms; to be useful, they must be
able to execute long, complicated algorithms on numerous data quickly  and
reliably.  A computer  carries out  an algorithm  as expressed  in one  of
several precisely  defined  languages  for  that  computer.  An  algorithm
expressed in a  language executable by  some actual computer  is called  a
program.

Programming,  the  design  of  programs, consists  of  two  parts,   often
interwoven:  the  design of  an  algorithm to  solve  a problem,  and  the
expression of that algorithm as a program within the limited notations  of
a particular computer language.  To learn to program,  you must learn  and
use some particular programming language, just as music is learned on some
particular instrument.   The  core  of learning  to  program,  though,  is
learning to design algorithms.

In CS106, we use the Pascal programming language. It is popular with users
of small to  medium-sized computers  (``micros'' and  ``minis''), and  has
become  a  common  language  for  communication  of  algorithms  in print.
Pascal is not as  well suited for the  expression of business problems  as
PL-I and  COBOL;  nor  as  well suited  for  engineering  calculations  as
FORTRAN; nor as well suited for processing symbolic information as  SNOBOL
and LISP; nor ...  well, you get  the idea. No matter.   Most of what  you
will want  to program  can  be said  very  similarly in  most  programming
languages, and after you learn one such language, you can learn any  other
in a day or so.

So, you will learn Pascal, and, with labor and attention, how to design an
algorithm systematically and correctly. You won't learn all of Pascal from
the course. This is no  oversight; parts of Pascal  are largely of use  to
more experienced programmers,  and parts are  of marginal usefulness.   If
you have trouble  with the problems,  it won't be  because you don't  know
Pascal well enough.

My goals are to teach you to systematically and correctly design  computer
programs more complicated  than anything  else you have  ever designed  in
your life, programs so sensitive to  error that a single mis-typed  symbol
will probably  make the  program incorrect.   Ideally, you  will learn  to
program in such a way that your first drafts of programs will contain  few
errors other  than  slips  of the  pen,  and  that your  programs  can  be
systematically tested and corrected (``debugged'').

Programming without  standards  of  quality  is  easy.  Programming  is  a
difficult discipline if one believes a program must be utterly trustworthy
on all valid data; that it must  detect and report all invalid data;  that
its results must be intelligible  and unambiguous; that other  programmers
must be  able to  adapt the  program to  other languages,  computers,  and
problems than those for which it  was originally designed, long after  the
original programmer has vanished.

The course notes are interlaced  with Rules of Good Programming  Practice.
These are only a small subset of the 927 (or was it 928?) eternal  truths,
but they are very useful,  and we expect you either  to  adhere to them or
(since they have exceptions) explain why.

We also  expect you  to take  responsibility for  yourself.  The  computer
center can be a difficult environment. The computer may fail for a day  at
a time.  Lines to  use the computer may  be hours long at  the end of  the
quarter.  Assignments may be more  difficult than intended. We expect  you
to begin projects as  early as possible; if  the computer fails six  hours
before a program is due,  that is your problem. We  expect you to use  the
often overloaded  computer system  in  a way  considerate to  your  fellow
students; in particular, when you no  longer are sure what you are  doing,
get off the computer and let someone else use it.  Also, delete any  files
you no longer need to release storage capacity for other users.  We expect
your programs to work for all valid data, and not just for the test  cases
you run; to deliberately design a program that only works for the data  on
which it is tested will be considered  cheating. We expect you to plan  to
spend twelve hours a week on  this course (the university guideline for  a
4-unit course) including class and computer time; you will find the course
insuitable as part of an 18-unit program.

We expect  you,  as the  assignments  become more  difficult,  to  include
adequate explanations  of how  your program  works. Let  the  hard-pressed
grader, who perhaps  just took the  course the previous  quarter, know  in
outline what your methods are. And if your native language is English,  we
would appreciate a demonstration of the fact. We expect you to respect the
privacy of other people's  computer files; the fact  that someone has  not
fully protected his files does not give you the right to read them.

Okay, we've told you the worst. On the good side, the teaching assistants,
consultants, and professor are there to  help out. Not by doing your  work
for you, but by serving as models of how to think about programming.  Most
of the  time, the  computer  center is  a  friendly environment.  And  the
computer itself is  the most versatile  tool you will  ever use. You  have
signed up to vastly  extend your powers to  use and create information.  I
think you will be glad you did.

ALGRMS[1, rfn]
		
		**American Programming's Plight**

		  prof. dr. Edsger W. Dijkstra
		  Burroughs Research Fellow
	
A competent programmer's most important assets are--perhaps in this order--
an excellent mastery of his native tongue and a considerable methematical
maturity. These facts are well-known and have been well-understood for more
than ten years.
By a sad accident of history they make programming, which is difficult anyhow,
in the USE even more